{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最大差值【中等】"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有一个列表，例如[10,4,2,6,4,3,9,8,5],\n",
    "\n",
    "求其中两个数x,y，\n",
    "\n",
    "满足x的索引小于y的索引，使得 y-x 最大。\n",
    "\n",
    "(这个示例的答案是x=2,y=9,最大值为7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#==============================答题区==============================#\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#==============================答题区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#==============================提示区==============================#\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#  提示：动态规划\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#==============================提示区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x= 2 ,y= 9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(2, 9)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#==============================答案区==============================#\n",
    "\n",
    "# 解题思路1：穷举法，n**2复杂度，效率偏低\n",
    "\n",
    "arr = [10,4,2,6,4,3,9,8,5]\n",
    "\n",
    "def f(arr):\n",
    "    assert len(arr)>2, \"len(arr) should > 2!\"\n",
    "    pairs = [(x,y) for i,x in enumerate(arr) \n",
    "             for j,y in enumerate(arr) if i<j]\n",
    "    diffs = [y-x for x,y in pairs]\n",
    "    maxdiff = max(diffs)\n",
    "    x,y = pairs[diffs.index(maxdiff)]\n",
    "    print(\"x=\",x,\",y=\",y)\n",
    "    \n",
    "    return(x,y)\n",
    "\n",
    "f(arr)\n",
    "\n",
    "#==============================答案区==============================#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x= 2 ,y= 9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(2, 9)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#==============================答案区==============================#\n",
    "\n",
    "# 解题思路2：动态规划法，只用扫描一遍，效率较高。\n",
    "# 动态规划的思想跟递归有些相似，用一些状态记录第k-1步时和目标相关的变量。\n",
    "# 如果在第k步时能够用合理的策略更新这些量，就可以往前推进。\n",
    "\n",
    "\n",
    "# 这里设置4个状态量：xmin记录之前扫描过的数当中的最小值,\n",
    "# maxdiff记录扫描到的满足条件的最大差值,\n",
    "# x,y记录取maxdiff时对应的x和y\n",
    "\n",
    "\n",
    "arr = [10,4,2,6,4,3,9,8,5]\n",
    "\n",
    "def f(arr):\n",
    "    assert len(arr)>2, \"len(arr) should > 2!\"\n",
    "    x,y = arr[0:2]\n",
    "    xmin = x\n",
    "    maxdiff = y-x\n",
    "    \n",
    "    for i in range(2,len(arr)):\n",
    "        if arr[i-1] < xmin:\n",
    "            xmin = arr[i-1]\n",
    "        if arr[i] - xmin > maxdiff:\n",
    "            maxdiff = arr[i] - xmin\n",
    "            x,y = xmin,arr[i]\n",
    "            \n",
    "    print(\"x=\",x,\",y=\",y)\n",
    "    return(x,y)\n",
    "\n",
    "f(arr)\n",
    "\n",
    "#==============================答案区==============================#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](../Python与算法之美.jpg)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
